//https://leetcode.cn/problems/permutations-ii/description/
//全排列2
//给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

void Creat(int* nums, int numsSize, int* returnSize, int pos, int* cur, bool* used, int** ret)
{
    if(pos == numsSize)
    {
        ret[*returnSize] = (int*)malloc(sizeof(int) * numsSize);
        memcpy(ret[*returnSize], cur, sizeof(int) * numsSize);
        (*returnSize)++;
        return;
    }
    else
    {
        bool usedNums[21] = {0};
        for(int i = 0; i < numsSize; i++)
        {
            int p = nums[i] + 10;
            if(used[i] == 0 && usedNums[p] == 0)
            {
                used[i] = 1;
                usedNums[p] = 1;
                cur[pos] = nums[i];
                Creat(nums, numsSize, returnSize, pos + 1, cur, used, ret);
                used[i] = 0;
            }
        }
    }
}

int** permuteUnique(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    *returnSize = 0;
    int* cur = (int*)malloc(sizeof(int) * numsSize);
    bool* used = (bool*)calloc(numsSize, sizeof(bool));
    int** ret = (int**)malloc(sizeof(int*) * 40320);

    Creat(nums, numsSize, returnSize, 0, cur, used, ret);

    ret = (int**)realloc(ret, sizeof(int*) * (*returnSize));
    *returnColumnSizes = (int*)malloc(sizeof(int) * (*returnSize));
    for(int i = 0; i < (*returnSize); i++)
    {
        (*returnColumnSizes)[i] = numsSize;
    }

    return ret;
}